//package work.rightAnswer;
//
//class KMP_28 {
//    public int strStr(String haystack, String needle) {
//        if(haystack.length()<needle.length()){
//            return -1;
//        }
//
//        int[] next = getNext(needle);
//
//        int j = 0;
//        for (int i = 0; i < haystack.length(); i++) {
//            while (j>0&&haystack.charAt(i)!=needle.charAt(j)){
//                j = next[j];
//            }
//            if(haystack.charAt(i)==needle.charAt(j)){
//                j++;
//            }
//            if (j==needle.length()){
//                return i - needle.length() +1;
//            }
//        }
//
//        return -1;
//    }
//
//    public int[] getNext(String needle){
//        if(needle.length()<2){
//            return new int[]{-1};
//        }
//        int[] next = new int[needle.length()];
//        next[0] = -1;
//        next[1] = 0;
//        int cn = 0;//cn 表示与i-1比较的下标位置  和 next[i-1]的值
//        int i = 2;//当前遍历下标位置
//        while (i<next.length){
//            if(needle.charAt(i-1)==needle.charAt(cn)){
//                next[i++] = ++cn;
//            } else if (cn>0) {
//                cn = next[cn];
//            }else {
//                next[i++] = 0;
//            }
//        }
//
//        return next;
//    }
//}